<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(B卷,100分)- 金字塔，BOSS的收入（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>微商模式比较典型&#xff0c;下级每赚 100 元就要上交 15 元&#xff0c;给出每个级别的收入&#xff0c;求出金字塔尖上的人收入。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>第一行输入N&#xff0c;表示有N个代理商上下级关系<br /> 接下来输入N行&#xff0c;每行三个数&#xff1a;</p> 
<blockquote> 
 <p>代理商代号 上级代理商代号 代理商赚的钱</p> 
</blockquote> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>输出一行&#xff0c;两个以空格分隔的整数&#xff0c;含义如下</p> 
<blockquote> 
 <p>金字塔顶代理商 最终的钱数</p> 
</blockquote> 
<p></p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">3<br /> 1 0 223<br /> 2 0 323<br /> 3 2 1203</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;"> <p>0 105</p> </td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;"> <p>2的最终收入等于323 &#43; 1203/100*15&#61;323 &#43; 180</p> <p>0的最终收入等于&#xff08;323 &#43; 180 &#43; 223&#xff09;/ 100 * 15 &#61; 105</p> </td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:84px;">输入</td><td style="width:414px;">4<br /> 1 0 100<br /> 2 0 200<br /> 3 0 300<br /> 4 0 200</td></tr><tr><td style="width:84px;">输出</td><td style="width:414px;">0 120</td></tr><tr><td style="width:84px;">说明</td><td style="width:414px;">无</td></tr></tbody></table> 
<p> </p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题的代理商结构其实就是一个树形结构&#xff0c;树根就是顶级代理商。</p> 
<p>因此&#xff0c;本题要求顶级代理商的钱&#xff0c;其实就是一个深搜过程&#xff0c;即每个父级代理商的钱 要从其所有子级商汲取&#xff08;每100元抽15元&#xff09;。</p> 
<p>本题的难点在于&#xff0c;不知道树根是哪个&#xff1f;即不知道顶级代理商号是多少。</p> 
<p>我的解题思路如下&#xff1a;</p> 
<ul><li>定义一个income字典&#xff0c;其key是代理商号&#xff0c;val是该代理商赚的钱</li><li>定义一个agents集合来记录所有出现过的代理商号</li><li>定义一个ch_fa字典&#xff0c;其key是子级代理商&#xff0c;val是父级代理商</li><li>定义一个fa_ch字典&#xff0c;其key是父级代理商&#xff0c;val是一个集合&#xff0c;记录key的所有子级代理商</li></ul> 
<p>而顶级代理商必然没有父级&#xff0c;因此&#xff0c;我们只要遍历agents&#xff0c;用被遍历到的每一个agent去ch_fa中找&#xff0c;如果找不到&#xff0c;则说明对应的agent就是顶级代理商号root。</p> 
<p></p> 
<p>找到顶级代理商号root后&#xff0c;提供fa_ch&#xff0c;找到root代理商的所有子代理商chs&#xff0c;然后遍历chs&#xff0c;得到每一个ch的赚的钱&#xff0c;从每个ch赚的钱中100抽15&#xff0c;汲取到root代理商赚的钱中。</p> 
<p>当然&#xff0c;每个ch赚的钱&#xff0c;也有来自于ch的子级代理商们&#xff0c;同样按照每100抽15的规则汲取。这是一个递归过程。</p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JS算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
let n, income, agents, ch_fa, fa_ch;

rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61; 1) {
    n &#61; parseInt(lines[0]);
    // income: 记录每个代理商赚的钱, key是代理商号, val是代理商赚的钱
    income &#61; {};
    // agents: 记录所有的代理商号
    agents &#61; [];
    // ch_fa: key是子级代理商号, val是父级代理商号
    ch_fa &#61; {};
    // fa_ch: key是父级代理上号, val是key的所有子级代理商号
    fa_ch &#61; {};
  }

  if (n &amp;&amp; lines.length &#61;&#61; n &#43; 1) {
    lines.shift();

    for (let s of lines) {
      // 子级代理商号,父级代理商号,子级代理商号赚的钱
      const [ch_id, fa_id, ch_income] &#61; s.split(&#34; &#34;);

      income[ch_id] &#61; parseInt(ch_income);

      agents.push(ch_id);
      agents.push(fa_id);

      ch_fa[ch_id] &#61; fa_id;

      if (!fa_ch[fa_id]) fa_ch[fa_id] &#61; [];
      if (!fa_ch[ch_id]) fa_ch[ch_id] &#61; [];

      fa_ch[fa_id].push(ch_id);
    }

    console.log(getResult());

    lines.length &#61; 0;
  }
});

function getResult() {
  for (let agent of agents) {
    // 顶级代理商号&#xff08;根&#xff09;没有父级
    if (!ch_fa[agent]) {
      // 设置顶级代理商号 初始金额 为0
      income[agent] &#61; 0;
      // 开始深搜
      dfs(agent);
      return &#96;${agent} ${income[agent]}&#96;;
    }
  }
}

function dfs(fa_id) {
  // 父级代理商号的所有子级代理商号chs
  const chs &#61; fa_ch[fa_id];

  // 如果存在子级代理商, 则父级代理商从每一个子级代理商赚的钱中&#xff1a;每100元抽15元
  if (chs.length &gt; 0) {
    for (let ch_id of chs) {
      dfs(ch_id);
      income[fa_id] &#43;&#61; Math.floor(income[ch_id] / 100) * 15;
    }
  }
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
  // income: 记录每个代理商赚的钱, key是代理商号, val是代理商赚的钱
  static HashMap&lt;String, Long&gt; income &#61; new HashMap&lt;&gt;();
  // agents: 记录所有的代理商号
  static ArrayList&lt;String&gt; agents &#61; new ArrayList&lt;&gt;();
  // ch_fa: key是子级代理商号, val是父级代理商号
  static HashMap&lt;String, String&gt; ch_fa &#61; new HashMap&lt;&gt;();
  // fa_ch: key是父级代理上号, val是key的所有子级代理商号
  static HashMap&lt;String, ArrayList&lt;String&gt;&gt; fa_ch &#61; new HashMap&lt;&gt;();

  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    int n &#61; sc.nextInt();

    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
      // 子级代理商号
      String ch_id &#61; sc.next();
      // 父级代理商号
      String fa_id &#61; sc.next();
      // 子级代理商号赚的钱
      long ch_income &#61; sc.nextLong();

      income.put(ch_id, ch_income);

      agents.add(ch_id);
      agents.add(fa_id);

      ch_fa.put(ch_id, fa_id);

      fa_ch.putIfAbsent(fa_id, new ArrayList&lt;&gt;());
      fa_ch.putIfAbsent(ch_id, new ArrayList&lt;&gt;());
      fa_ch.get(fa_id).add(ch_id);
    }

    System.out.println(getResult());
  }

  public static String getResult() {
    for (String agent : agents) {
      // 顶级代理商号&#xff08;根&#xff09;没有父级
      if (!ch_fa.containsKey(agent)) {
        // 设置顶级代理商号 初始金额 为0
        income.put(agent, 0L);
        // 开始深搜
        dfs(agent);
        return agent &#43; &#34; &#34; &#43; income.get(agent);
      }
    }

    return &#34;&#34;;
  }

  public static void dfs(String fa_id) {
    // 父级代理商号的所有子级代理商号chs
    ArrayList&lt;String&gt; chs &#61; fa_ch.get(fa_id);

    // 如果存在子级代理商, 则父级代理商从每一个子级代理商赚的钱中&#xff1a;每100元抽15元
    if (chs.size() &gt; 0) {
      for (String ch_id : chs) {
        dfs(ch_id);
        income.put(fa_id, income.get(fa_id) &#43; income.get(ch_id) / 100 * 15);
      }
    }
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
n &#61; int(input())

# income: 记录每个代理商赚的钱, key是代理商号, val是代理商赚的钱
income &#61; {}
# agents: 记录所有的代理商号
agents &#61; []
# ch_fa: key是子级代理商号, val是父级代理商号
ch_fa &#61; {}
# fa_ch: key是父级代理上号, val是key的所有子级代理商号
fa_ch &#61; {}

for _ in range(n):
    # 子级代理商号,父级代理商号,子级代理商号赚的钱
    ch_id, fa_id, ch_income &#61; input().split()

    income[ch_id] &#61; int(ch_income)

    agents.append(ch_id)
    agents.append(fa_id)

    ch_fa[ch_id] &#61; fa_id

    fa_ch.setdefault(fa_id, [])
    fa_ch.setdefault(ch_id, [])

    fa_ch[fa_id].append(ch_id)


def dfs(fa):
    # 父级代理商号的所有子级代理商号chs
    chs &#61; fa_ch[fa]

    # 如果存在子级代理商, 则父级代理商从每一个子级代理商赚的钱中&#xff1a;每100元抽15元
    if len(chs) &gt; 0:
        for ch in chs:
            dfs(ch)
            income[fa] &#43;&#61; income[ch] // 100 * 15


# 算法入口
def getResult():
    for agent in agents:
        # 顶级代理商号&#xff08;根&#xff09;没有父级
        if ch_fa.get(agent) is None:
            # 设置顶级代理商号 初始金额 为0
            income[agent] &#61; 0
            # 开始深搜
            dfs(agent)
            return f&#34;{agent} {income[agent]}&#34;


# 算法调用
print(getResult())
</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>